{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Max Value of Equation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #queue #array #sliding-window #monotonic-queue #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #队列 #数组 #滑动窗口 #单调队列 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMaxValueOfEquation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #满足不等式的最大值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组 <code>points</code> 和一个整数 <code>k</code> 。数组中每个元素都表示二维平面上的点的坐标，并按照横坐标 x 的值从小到大排序。也就是说 <code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> ，并且在 <code>1 &lt;= i &lt; j &lt;= points.length</code> 的前提下， <code>x<sub>i</sub> &lt; x<sub>j</sub></code> 总成立。</p>\n",
    "\n",
    "<p>请你找出<em> </em><code>y<sub>i</sub>&nbsp;+ y<sub>j</sub>&nbsp;+ |x<sub>i</sub>&nbsp;- x<sub>j</sub>|</code> 的 <strong>最大值</strong>，其中 <code>|x<sub>i</sub>&nbsp;- x<sub>j</sub>|&nbsp;&lt;= k</code> 且 <code>1 &lt;= i &lt; j &lt;= points.length</code>。</p>\n",
    "\n",
    "<p>题目测试数据保证至少存在一对能够满足 <code>|x<sub>i</sub>&nbsp;- x<sub>j</sub>|&nbsp;&lt;= k</code> 的点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>points = [[1,3],[2,0],[5,10],[6,-10]], k = 1\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>前两个点满足 |x<sub>i</sub>&nbsp;- x<sub>j</sub>| &lt;= 1 ，代入方程计算，则得到值 3 + 0 + |1 - 2| = 4 。第三个和第四个点也满足条件，得到值 10 + -10 + |5 - 6| = 1 。\n",
    "没有其他满足条件的点，所以返回 4 和 1 中最大的那个。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>points = [[0,0],[3,0],[9,2]], k = 3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>只有前两个点满足 |x<sub>i</sub>&nbsp;- x<sub>j</sub>| &lt;= 3 ，代入方程后得到值 0 + 0 + |0 - 3| = 3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= points.length &lt;= 10^5</code></li>\n",
    "\t<li><code>points[i].length == 2</code></li>\n",
    "\t<li><code>-10^8&nbsp;&lt;= points[i][0], points[i][1] &lt;= 10^8</code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 2 * 10^8</code></li>\n",
    "\t<li>对于所有的<code>1 &lt;= i &lt; j &lt;= points.length</code> ，<code>points[i][0] &lt; points[j][0]</code> 都成立。也就是说，<code>x<sub>i</sub></code> 是严格递增的。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [max-value-of-equation](https://leetcode.cn/problems/max-value-of-equation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [max-value-of-equation](https://leetcode.cn/problems/max-value-of-equation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,3],[2,0],[5,10],[6,-10]]\\n1', '[[0,0],[3,0],[9,2]]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        n = len(points)\n",
    "        deque = [[0,0] for _ in range(n)]\n",
    "        ans = -0x7fffffff\n",
    "        h = t = 0\n",
    "        for i in range(n):\n",
    "            x = points[i][0]\n",
    "            y = points[i][1]\n",
    "            while h<t and x-deque[h][0]>k:\n",
    "                h += 1\n",
    "            if h<t:\n",
    "                ans = max(ans,y+x+deque[h][1]-deque[h][0])\n",
    "            while h<t and deque[t-1][1]-deque[t-1][0]<=y-x:\n",
    "                t -= 1\n",
    "            deque[t][0] = x\n",
    "            deque[t][1] = y\n",
    "            t += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        res = -float('inf')\n",
    "        heap = []\n",
    "        for xi, yi in sorted(points):\n",
    "            while len(heap):\n",
    "                vj, xj = heap[0]\n",
    "                if xj < xi - k:\n",
    "                    heapq.heappop(heap)\n",
    "                else:\n",
    "                    res = max(res, xi + yi - vj)\n",
    "                    break\n",
    "            heapq.heappush(heap, (xi - yi, xi))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# import math\n",
    "# from typing import List\n",
    "#\n",
    "#\n",
    "# class Solution:\n",
    "#     def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "#         n = len(points)\n",
    "#         ans = -math.inf\n",
    "#         R = 1   # given i, the smallest index s.t. x_{R} - x_{i} <= k\n",
    "#         M = -1   # given i, the index M < R s.t. the value is maximized\n",
    "#         get_value = lambda i, j: points[i][1] + points[j][1] + (points[j][0] - points[i][0])\n",
    "#         for i in range(n-1):\n",
    "#             while R < n and points[R][0] - points[i][0] <= k:\n",
    "#                 if M <= i or get_value(i, M) <= get_value(i, R):\n",
    "#                     M = R\n",
    "#                 R += 1\n",
    "#\n",
    "#             if R >= n:\n",
    "#                 # the remaining points are close to each other\n",
    "#                 max_sum_pair = sum(points[-1])\n",
    "#                 for j in reversed(range(i, n-1)):\n",
    "#                     ans = max(ans, points[j][1] - points[j][0] + max_sum_pair)\n",
    "#                     max_sum_pair = max(max_sum_pair, points[j][0] + points[j][1])\n",
    "#                 break\n",
    "#             else:\n",
    "#                 print(i, M, get_value(i, M))\n",
    "#                 ans = max(ans, get_value(i, M))\n",
    "#         return ans\n",
    "#\n",
    "# points = [[-19,-12],[-13,-18],[-12,18],[-11,-8],[-8,2],[-7,12],[-5,16],[-3,9],[1,-7],[5,-4],[6,-20],[10,4],[16,4],[19,-9],[20,19]]\n",
    "# k = 6\n",
    "# solution = Solution()\n",
    "# print(solution.findMaxValueOfEquation(points, k))\n",
    "import bisect\n",
    "import math\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        sum_of_pairs = [sum(points[0])]\n",
    "        R = 1   # given i, the minimal R s.t. points[i: R] are closed to each other\n",
    "        n = len(points)\n",
    "        ans = -math.inf\n",
    "        for i in range(n-1):\n",
    "            if R == i:\n",
    "                R = i+1\n",
    "            else:\n",
    "                sum_of_pairs.pop(bisect.bisect_left(sum_of_pairs, sum(points[i])))\n",
    "            while R < n and (points[R][0] - points[i][0]) <= k:\n",
    "                bisect.insort(sum_of_pairs, sum(points[R]))\n",
    "                R += 1\n",
    "            if R >= n:\n",
    "                # the remaining points are close to each other\n",
    "                max_sum_pair = sum(points[-1])\n",
    "                for j in reversed(range(i, n-1)):\n",
    "                    ans = max(ans, points[j][1] - points[j][0] + max_sum_pair)\n",
    "                    max_sum_pair = max(max_sum_pair, points[j][0] + points[j][1])\n",
    "                break\n",
    "            if sum_of_pairs:\n",
    "                ans = max(ans, points[i][1] - points[i][0] + sum_of_pairs[-1])\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        res = -inf\n",
    "        heap = []\n",
    "        for x, y in points:\n",
    "            while heap and x - heap[0][1] > k:\n",
    "                heappop(heap)\n",
    "            if heap:\n",
    "                res = max(res, x + y - heap[0][0])\n",
    "            heappush(heap, [x - y, x])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        res = -inf\n",
    "        heap = []\n",
    "        for x, y in points:\n",
    "            while heap and x - heap[0][1] > k:\n",
    "                heappop(heap)\n",
    "            if heap:\n",
    "                res = max(res, x + y - heap[0][0])\n",
    "            heappush(heap, [x - y, x])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        res = -inf\n",
    "        heap = []\n",
    "        for x, y in points:\n",
    "            while heap and x - heap[0][1] > k:\n",
    "                heappop(heap)\n",
    "            if heap:\n",
    "                res = max(res, x + y - heap[0][0])\n",
    "            heappush(heap, [x - y, x])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        res = -inf\n",
    "        heap = []\n",
    "        for x, y in points:\n",
    "            while heap and x - heap[0][1] > k:\n",
    "                heappop(heap)\n",
    "            if heap:\n",
    "                res = max(res, x + y - heap[0][0])\n",
    "            heappush(heap, [x - y, x])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        res = -float('inf')      \n",
    "        hp = []\n",
    "        for x, y in points:\n",
    "            while hp and x - hp[0][1] > k:\n",
    "                heappop(hp)\n",
    "            if hp:\n",
    "                res = max(res, x + y - hp[0][0])\n",
    "            heappush(hp, [x - y , x])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        res = []\n",
    "        for a, b in points:\n",
    "            res.append(b - a)\n",
    "        ans = -inf\n",
    "        q = deque()\n",
    "        max_q = deque()\n",
    "        for i, (x, y) in enumerate(points):\n",
    "            while q and x > points[q[0]][0] + k:\n",
    "                j = q.popleft()\n",
    "                if j == max_q[0]:\n",
    "                    max_q.popleft()\n",
    "            if q:\n",
    "                ans = max(ans, res[max_q[0]] + x + y)\n",
    "            q.append(i)\n",
    "            while max_q and res[max_q[-1]] <= res[i]:\n",
    "                max_q.pop()\n",
    "            max_q.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        q = deque()\n",
    "        ans = -0x3f3f3f3f\n",
    "        right = 0\n",
    "        for i in range(len(points)):\n",
    "            x1, y1 = points[i]\n",
    "            while q and q[0][1]<=i:\n",
    "                q.popleft()\n",
    "            while right<len(points) and points[right][0]<=x1+k:\n",
    "                x2, y2 = points[right]\n",
    "                while q and q[-1][0]<x2+y2:\n",
    "                    q.pop()\n",
    "                if right>i:\n",
    "                    q.append((x2+y2, right))\n",
    "                right += 1\n",
    "            if q:\n",
    "                print(i, q, y1+q[0][0]-x1)\n",
    "                ans = max(ans, y1+q[0][0]-x1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "#         ans = -inf\n",
    "#         q = deque()\n",
    "#         for x, y in points:\n",
    "#             while q and x - q[0][0] > k:\n",
    "#                 q.popleft()\n",
    "#             if q:\n",
    "#                 ans = max(ans, x + y + q[0][1] - q[0][0])\n",
    "#                 #维护一个单调递减栈\n",
    "#             while q and y - x >= q[-1][1] - q[-1][0]:\n",
    "#                 q.pop()\n",
    "#             q.append((x, y))\n",
    "#         return ans\n",
    "\n",
    "\n",
    "#堆存最大的x-y\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        ans = -inf\n",
    "        pq = []\n",
    "        for x, y in points:\n",
    "            while pq and x - pq[0][1] > k:\n",
    "                heappop(pq)\n",
    "            if pq:\n",
    "                ans = max(ans, x + y - pq[0][0])\n",
    "            heappush(pq, (x - y, x))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        res = -inf\n",
    "        q = []\n",
    "        for x, y in points:\n",
    "            while q and x - q[0][1] > k:\n",
    "                heappop(q)\n",
    "            if q:\n",
    "                res = max(res, x + y - q[0][0])\n",
    "            heappush(q, (x - y, x))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        res = -inf\n",
    "        heap =[]\n",
    "        for x, y in points:\n",
    "            while heap and x-heap[0][1] > k:\n",
    "                heappop(heap)\n",
    "            if heap:\n",
    "                res = max(res, x+y-heap[0][0])\n",
    "            heappush(heap, [x-y, x])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        res = -inf\n",
    "        heap = []\n",
    "        for x, y in points:\n",
    "            while heap and x - heap[0][1] > k:\n",
    "                heappop(heap)\n",
    "            if heap:\n",
    "                res = max(res, x + y - heap[0][0])\n",
    "            heappush(heap, [x - y, x])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "\n",
    "        ans = -200000000\n",
    "        pq = []\n",
    "\n",
    "        for x,y in points:\n",
    "            while pq and x-pq[0][1] > k:\n",
    "                heapq.heappop(pq)\n",
    "\n",
    "            if(pq):\n",
    "                ans = max(ans,x+y-pq[0][0])\n",
    "\n",
    "\n",
    "            heapq.heappush(pq,[x-y,x])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "\n",
    "        # 遍历，这么说? ,遍历得最大长度为 k\n",
    "        # 滑动窗口\n",
    "        # res = -inf\n",
    "        # for i in range(len(points)):\n",
    "        #     # 最长为多少，最后一个点的 x 坐标，当然我们也可以不适用x坐标而是用点来确定\n",
    "\n",
    "        #     # 滑动窗口\n",
    "        #     j = 1\n",
    "        #     while i + j < len(points) and points[i + j][0] < points[i][0] + k:\n",
    "        #         # 滑动窗口\n",
    "        #         res = max(res, points[i][1] + points[i + j][1]\n",
    "        #                   + points[i + j][0] - points[i][0])\n",
    "        #         j += 1\n",
    "        # return res\n",
    "\n",
    "        res = -inf\n",
    "\n",
    "        heap = [] # 堆中放了什么？？？  放了 x - y 的值，这是一个小根堆，每次我们都弹出不符合条件的小根堆，没啥用，我们需要找到最大的 -x + y ,也就是最小的符合条件的 y-x\n",
    "\n",
    "        for x,y in points:\n",
    "            while heap and x - heap[0][1] > k: \n",
    "                heapq.heappop(heap) # 弹出堆顶元素\n",
    "                # 弹出不符合条件的值\n",
    "            if heap:\n",
    "                res = max(res, x + y -  heap[0][0])\n",
    "            heapq.heappush(heap, (x - y, x))    \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        res = -inf\n",
    "        heap = []\n",
    "        for x, y in points:\n",
    "            while heap and x - heap[0][1] > k:\n",
    "                heappop(heap)\n",
    "            if heap:\n",
    "                res = max(res, x + y - heap[0][0])\n",
    "            heappush(heap, [x - y, x])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from heapq import heappush, heappop \n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        # return self.findMaxValueOfEquationByMonototicQueue(points, k)\n",
    "        return self.findMaxValueOfEquationByHeap(points, k)\n",
    "\n",
    "    def findMaxValueOfEquationByMonototicQueue(self, points: List[list[int]], k: int) -> int:\n",
    "        monototicQueue = deque([])\n",
    "        # 存[(y-x),x]\n",
    "        ans = float('-inf')\n",
    "        for point in points:\n",
    "            x, y = point \n",
    "            while monototicQueue and x - monototicQueue[0][1] > k:\n",
    "                monototicQueue.popleft() \n",
    "            if monototicQueue and ans < x + y + monototicQueue[0][0]:\n",
    "                ans =  x + y + monototicQueue[0][0] \n",
    "            while monototicQueue and y - x >= monototicQueue[-1][0]:\n",
    "                monototicQueue.pop() \n",
    "            monototicQueue.append([y - x, x])\n",
    "        return ans \n",
    " \n",
    "    def findMaxValueOfEquationByHeap(self, points: List[list[int]], k: int) -> int:\n",
    "        samllRootHeap = [] \n",
    "        # 存[(x - y), x], 堆顶元素最小，则 -1*samllRootHeap[0][0]最大\n",
    "        # 计算 xj + yj + (yi - xi)的最大值\n",
    "        ans = float('-inf')\n",
    "        for point in points:\n",
    "            x, y = point \n",
    "            while samllRootHeap and x - samllRootHeap[0][1] > k:\n",
    "                heappop(samllRootHeap) \n",
    "            if samllRootHeap and ans < x + y - samllRootHeap[0][0]:\n",
    "                ans = x + y - samllRootHeap[0][0] \n",
    "            heappush(samllRootHeap, [x - y, x])\n",
    "        return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        res = float('-inf')\n",
    "        queue = []\n",
    "        for x, y in points:\n",
    "            while queue and x - queue[0][1] > k:\n",
    "                heapq.heappop(queue)\n",
    "            if queue:\n",
    "                res = max(res, x+y-queue[0][0])\n",
    "            heapq.heappush(queue, [x-y, x])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        max_sum = float('-inf')  # 初始化最大值为负无穷\n",
    "        heap = []  # 创建一个空堆\n",
    "        \n",
    "        for x, y in points:\n",
    "            # 移除不满足条件的元素，即 x - heap[0][1] > k 的元素\n",
    "            while heap and x - heap[0][1] > k:\n",
    "                heapq.heappop(heap)\n",
    "            \n",
    "            if heap:\n",
    "                # 计算当前点和堆顶点的最大值，并更新最大值\n",
    "                max_sum = max(max_sum, x + y - heap[0][0])\n",
    "            \n",
    "            # 将当前点的信息 [x - y, x] 添加到堆中\n",
    "            heapq.heappush(heap, [x - y, x])\n",
    "        \n",
    "        return max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        MIN = -200000000\n",
    "        ans = MIN\n",
    "        n = len(points)\n",
    "        score = [x[0] + x[1] for x in points] + [MIN]\n",
    "        l, r = 0, 1\n",
    "        pMax = -1\n",
    "        while l < n:\n",
    "            if pMax <= l:\n",
    "                pMax = -1\n",
    "                for i in range(l + 1, r):\n",
    "                    if score[i] > score[pMax]:\n",
    "                        pMax = i\n",
    "            while r < n and points[r][0] <= points[l][0] + k:\n",
    "                if score[r] > score[pMax]:\n",
    "                    pMax = r\n",
    "                r += 1\n",
    "            \n",
    "            if score[pMax] > MIN:\n",
    "                ans = max(ans, points[l][1] - points[l][0] + score[pMax])\n",
    "            l += 1\n",
    "            if l == r:\n",
    "                r += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        res = -inf\n",
    "        heap = []\n",
    "        for x, y in points:\n",
    "            while heap and x - heap[0][1] > k:\n",
    "                heappop(heap)\n",
    "            if heap:\n",
    "                res = max(res, x + y - heap[0][0])\n",
    "            heappush(heap, [x - y, x])\n",
    "        return res\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/max-value-of-equation/solutions/2351324/man-zu-bu-deng-shi-de-zui-da-zhi-by-leet-5rbj/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import deque\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        # (yi -xi) + (xj + yj)\n",
    "        # 单向队列\n",
    "        q = deque()\n",
    "        max_value = float('-inf')\n",
    "        for xj, yj in points:\n",
    "            while q:\n",
    "                (yi_xi, xi) = q[0]\n",
    "                if xj - xi > k:\n",
    "                    q.popleft()\n",
    "                    continue\n",
    "                value = yi_xi +  xj + yj\n",
    "                if value  > max_value:\n",
    "                    max_value = value\n",
    "                break\n",
    "            yi_xi = yj - xj\n",
    "            while q and q[-1][0] < yi_xi:\n",
    "                q.pop()\n",
    "            q.append((yi_xi, xj))\n",
    "        return max_value\n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        res = -inf\n",
    "        heap = []\n",
    "        for x, y in points:\n",
    "            while heap and x - heap[0][1] > k:\n",
    "                heappop(heap)\n",
    "            if heap:\n",
    "                res = max(res, x + y - heap[0][0])\n",
    "            heappush(heap, [x - y, x])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import deque\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        # (yi -xi) + (xj + yj)\n",
    "        # 单向队列\n",
    "        q = deque()\n",
    "        max_value = float('-inf')\n",
    "        for j, (xj, yj) in enumerate(points):\n",
    "            while q:\n",
    "                (yi_xi, xi) = q[0]\n",
    "                if xj - xi > k:\n",
    "                    q.popleft()\n",
    "                    continue\n",
    "                value = yi_xi +  xj + yj\n",
    "                if value  > max_value:\n",
    "                    max_value = value\n",
    "                break\n",
    "            yi_xi = yj - xj\n",
    "            while q and q[-1][0] < yi_xi:\n",
    "                q.pop()\n",
    "            q.append((yi_xi, xj))\n",
    "        return max_value\n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        q = deque()\n",
    "        ans = -inf\n",
    "        # (yi-xi) + (yj+xj)\n",
    "        for x,y in points:\n",
    "            while q and q[0][1] +k < x:\n",
    "                q.popleft()\n",
    "            if q:\n",
    "                ans = max(ans,q[0][0] + x + y)\n",
    "            while q and q[-1][0] <= y-x:\n",
    "                q.pop()\n",
    "            q.append((y-x,x))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        # yi + yj + xj - xi\n",
    "        # yi - xi + xj + yj j固定，求yi - xi的最大值，窗口大小k\n",
    "        q = deque()\n",
    "        ans = -inf\n",
    "        g = [y - x for x,y in points]\n",
    "\n",
    "        for i,[x,y] in enumerate(points):\n",
    "            while q and x - points[q[0]][0] > k:\n",
    "                q.popleft()\n",
    "            if q:\n",
    "                ans = max(ans,x + y + g[q[0]])\n",
    "            while q and g[q[-1]] <= g[i]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        # max(y_i+y_j+|x_i-x_j|)=max(y_j+x_j)+max(y_i-x_i) (i<j)\n",
    "        add_list=[point[1]+point[0] for point in points]\n",
    "        minus_list=[point[1]-point[0] for point in points]\n",
    "        queue=[]\n",
    "        result=-float('inf')\n",
    "\n",
    "        for i in range(1,len(points)):\n",
    "            # 第一步，如果queue中的x_j不满足条件，则删去\n",
    "            while queue!=[] and points[i][0]-queue[0][0]>k:\n",
    "                queue.pop(0)\n",
    "            # 第二步，如果x_{i-1}满足条件，则将其加入到queue，并且比minus_list[i-1]小的元素要全部弹出来\n",
    "            if points[i][0]-points[i-1][0]<=k:\n",
    "                while queue!=[] and queue[-1][1]<minus_list[i-1]:\n",
    "                    queue.pop()\n",
    "                queue.append((points[i-1][0],minus_list[i-1]))\n",
    "            # 第三步，queue中存放的是从大到小排列的符合x_i要求的minus值\n",
    "            if queue!=[]:\n",
    "                result=max(result,add_list[i]+queue[0][1])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        # 平面点集，一个维度排序，另一个维度数据结构\n",
    "        # 双指针+有序集合\n",
    "        # yi + yj + xj - xi\n",
    "        # sl = SortedList()\n",
    "        # l, r = 0, 0\n",
    "        # n = len(points)\n",
    "        # res = -inf\n",
    "        # while r < n:\n",
    "        #     while points[r][0] - points[l][0] > k:\n",
    "        #         sl.pop(sl.bisect_left(points[l][1] - points[l][0]))\n",
    "        #         l += 1\n",
    "        #     if sl: res = max(res, points[r][1] + points[r][0] + sl[-1])\n",
    "        #     sl.add(points[r][1] - points[r][0])\n",
    "        #     r += 1\n",
    "\n",
    "        # return res\n",
    "        # 单调队列\n",
    "        dq = deque()\n",
    "        res = -inf\n",
    "        for x, y in points:\n",
    "            while dq and dq[0][0] + k < x: dq.popleft()\n",
    "            if dq: res = max(res, x + y + dq[0][1])\n",
    "            while dq and dq[-1][1] <= y - x: dq.pop()\n",
    "            dq.append((x, y - x))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        left = 0\n",
    "        q = []\n",
    "        ans = float('-inf')\n",
    "        heapq.heappush(q, (points[0][0] - points[0][1], 0))\n",
    "        for right, point in enumerate(points[1:], start=1):\n",
    "\n",
    "            while points[right][0] - points[left][0] > k:\n",
    "                left += 1\n",
    "\n",
    "            while q and q[0][1] < left:\n",
    "                heapq.heappop(q)\n",
    "            if q:\n",
    "                v, i = q[0]\n",
    "                ans = max(ans, point[1] + point[0] - v)\n",
    "            heapq.heappush(q, (points[right][0] - points[right][1], right))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        return func1(points, k)\n",
    "\n",
    "def func1(points, k):\n",
    "    maximum = -float(\"inf\")\n",
    "    left_pos = 0\n",
    "    max_y_minus_x = -float(\"inf\")   #\n",
    "    max_y_minus_x_index = -1\n",
    "    for pos in range(1, len(points)):\n",
    "        x_pos, y_pos = points[pos]\n",
    "        while left_pos < pos and points[left_pos][0] < x_pos - k:\n",
    "            left_pos += 1        \n",
    "        if left_pos == pos:\n",
    "            continue\n",
    "                    \n",
    "        if max_y_minus_x_index >= left_pos:\n",
    "            ifrom = pos-1\n",
    "        else:\n",
    "            ifrom = left_pos\n",
    "            max_y_minus_x = -float(\"inf\")\n",
    "            \n",
    "        for i in range(ifrom, pos):\n",
    "            x, y = points[i]\n",
    "            dif = y - x\n",
    "            if dif >= max_y_minus_x:\n",
    "                max_y_minus_x = dif\n",
    "                max_y_minus_x_index = i\n",
    "\n",
    "        maximum = max(maximum, y_pos + x_pos + max_y_minus_x)\n",
    "    return maximum\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        res = -inf\n",
    "        q = deque()\n",
    "        for x, y in points:\n",
    "            while q and x - q[0][1] > k:\n",
    "                q.popleft()\n",
    "            if q:\n",
    "                res = max(res, x + y + q[0][0])\n",
    "            while q and y - x >= q[-1][0]:\n",
    "                q.pop()\n",
    "            q.append([y - x, x])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        res = float('-inf')\n",
    "        queue = []\n",
    "        for x, y in points:\n",
    "            while queue and x - queue[0][1] > k:\n",
    "                queue.pop(0)\n",
    "            if queue:\n",
    "                res = max(res, x+y+queue[0][0])\n",
    "            while queue and queue[-1][0] <= y-x:\n",
    "                queue.pop()\n",
    "            queue.append([y-x, x])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        t = 0\n",
    "        h = 0\n",
    "        ans = -1000000000\n",
    "        n = len(points)\n",
    "        arr = [0 for _ in range(200000)]\n",
    "        for i in range(n):\n",
    "            while h < t and points[i][0] - points[arr[h]][0] > k:\n",
    "                h += 1\n",
    "            if h < t:\n",
    "                ans = max(ans, points[i][1] + points[i][0] + points[arr[h]][1] - points[arr[h]][0]) \n",
    "            while h < t and points[i][1] - points[i][0] >= points[arr[t-1]][1] - points[arr[t-1]][0]:\n",
    "                t -= 1\n",
    "            arr[t] = i\n",
    "            t += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        ans = -inf\n",
    "        q = deque()\n",
    "        for x, y in points:\n",
    "            while q and q[0][0] < x - k:  # 队首超出范围\n",
    "                q.popleft()  # 弹它！\n",
    "            if q:\n",
    "                ans = max(ans, x + y + q[0][1])  # 加上最大的 yi-xi\n",
    "            while q and q[-1][1] <= y - x:  # 队尾不如新来的强\n",
    "                q.pop()  # 弹它！\n",
    "            q.append((x, y - x))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        dq = deque()\n",
    "        ans = -inf\n",
    "        for x, y in points:\n",
    "            while dq and x - dq[0][0] > k:\n",
    "                dq.popleft()\n",
    "            if dq:\n",
    "                ans = max(ans, x - dq[0][0] + y + dq[0][1])\n",
    "            while dq and y - x >= dq[-1][1] - dq[-1][0]:\n",
    "                dq.pop()\n",
    "            dq.append((x, y))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        '''\n",
    "        result = -2147483647\n",
    "        ptl = 0\n",
    "        ptr = 1\n",
    "        while ptr < len(points):\n",
    "            if points[ptr][0] - points[ptl][0] > k:\n",
    "                ptl += 1\n",
    "                if ptl == ptr:\n",
    "                    ptr += 1\n",
    "                continue\n",
    "            value = points[ptl][1] + points[ptr][1] + abs(points[ptr][0]-points[ptl][0])\n",
    "            result = max(value, result)\n",
    "            ptl += 1\n",
    "            if ptr < len(points)-1 and points[ptr][1] * 2 < value or ptl == ptr:\n",
    "                ptr += 1\n",
    "        '''\n",
    "        res = -inf\n",
    "        heap = []\n",
    "        for x, y in points:\n",
    "            while heap and x - heap[0][1] > k:\n",
    "                heappop(heap)\n",
    "            if heap:\n",
    "                res = max(res, x + y - heap[0][0])\n",
    "            heappush(heap, [x - y, x])\n",
    "        return res\n",
    "        '''\n",
    "        for i in range(0,len(points)-1):\n",
    "            for j in range(i+1,len(points)):\n",
    "                if abs(points[j][0] - points[i][0]) > k:\n",
    "                    break\n",
    "                else:\n",
    "                    value = points[i][1] + points[j][1] + abs(points[j][0]-points[i][0])\n",
    "                    if value > result:\n",
    "                        result = value\n",
    "        \n",
    "        return result\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        ans = -inf\n",
    "        q = deque()\n",
    "        for x, y in points:\n",
    "            while q and q[0][0] < x - k:  # 队首超出范围\n",
    "                q.popleft()  # 弹它！\n",
    "            if q:\n",
    "                ans = max(ans, x + y + q[0][1])  # 加上最大的 yi-xi\n",
    "            while q and q[-1][1] <= y - x:  # 队尾不如新来的强\n",
    "                q.pop()  # 弹它！\n",
    "            q.append((x, y - x))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        ans = -inf\n",
    "        q = deque()\n",
    "        for x, y in points:\n",
    "            while q and q[0][0] < x - k:  # 队首超出范围\n",
    "                q.popleft()  # 弹它！\n",
    "            if q:\n",
    "                ans = max(ans, x + y + q[0][1])  # 加上最大的 yi-xi\n",
    "            while q and q[-1][1] <= y - x:  # 队尾不如新来的强\n",
    "                q.pop()  # 弹它！\n",
    "            q.append((x, y - x))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        # (x, y-x)\n",
    "        # 单调队列确保队首是当前滑动窗口中y-x的最大值\n",
    "        ans = -inf\n",
    "        q = deque()\n",
    "        # for x, y in points:\n",
    "        #     while q and x - q[0][0] > k:\n",
    "        #         q.popleft()\n",
    "        #     if len(q)>0:\n",
    "        #         ans = max(ans, x+y+q[0][1])\n",
    "        #     while q and y-x >= q[-1][1]:\n",
    "        #         q.pop()\n",
    "        #     q.append([x, y-x])\n",
    "            \n",
    "        # return ans\n",
    "        # 存储i\n",
    "        for i, (x, y) in enumerate(points):\n",
    "            while q and x - points[q[0]][0] > k:\n",
    "                q.popleft()\n",
    "            if q:\n",
    "                ans = max(ans, x+y+points[q[0]][1]-points[q[0]][0])\n",
    "            while q and y-x >= points[q[-1]][1]-points[q[-1]][0]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        n = len(points)\n",
    "        j = 0\n",
    "        st = collections.deque()\n",
    "        ans = -inf\n",
    "\n",
    "        for i, (xi, yi) in enumerate(points):\n",
    "            while j < n and points[j][0] <= xi + k:\n",
    "                xy = sum(points[j])\n",
    "                while st and xy >= sum(points[st[-1]]):\n",
    "                    st.pop()\n",
    "                st.append(j)\n",
    "                j += 1\n",
    "\n",
    "            while st and st[0] <= i:\n",
    "                st.popleft()\n",
    "                \n",
    "            if st:\n",
    "                xj, yj = points[st[0]]\n",
    "                ans = max(ans, yi - xi + xj + yj)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        ans = -inf\n",
    "        q = deque()\n",
    "        for x, y in points:\n",
    "            while q and q[0][0] < x - k:  # 队首超出范围\n",
    "                q.popleft()  # 弹它！\n",
    "            if q:\n",
    "                ans = max(ans, x + y + q[0][1])  # 加上最大的 yi-xi\n",
    "            while q and q[-1][1] <= y - x:  # 队尾不如新来的强\n",
    "                q.pop()  # 弹它！\n",
    "            q.append((x, y - x))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        q = deque()\n",
    "        ans = -inf \n",
    "        for x, y in points:\n",
    "            while q and q[0][0] < x - k:\n",
    "                q.popleft()\n",
    "            if q:\n",
    "                ans = max(ans, x + y + q[0][1])\n",
    "            while q and q[-1][1] <= y - x:\n",
    "                q.pop()\n",
    "            q.append((x, y - x))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        mx = deque()\n",
    "        ans = -inf\n",
    "        for i, (x, y) in enumerate(points):\n",
    "\n",
    "            # 出 \n",
    "            while mx and x - points[mx[0]][0] > k:\n",
    "                mx.popleft()\n",
    "\n",
    "            if mx:\n",
    "                ans = max(ans, points[mx[0]][1] - points[mx[0]][0] + x + y)\n",
    "\n",
    "                  # 入 \n",
    "            while mx and points[mx[-1]][1] - points[mx[-1]][0] <= y - x:\n",
    "                mx.pop()\n",
    "\n",
    "            mx.append(i)\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        res = -inf\n",
    "        q = deque()  # 记录(yi - xi, xi) 递减\n",
    "        # xj + yj + yi - xi\n",
    "        for x, y in points:\n",
    "            while q and x - q[0][1] > k:\n",
    "                q.popleft()\n",
    "            if q:\n",
    "                res = max(res, x + y + q[0][0])\n",
    "            while q and q[-1][0] < y - x:\n",
    "                q.pop()\n",
    "            q.append((y - x, x))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        ans=-inf\n",
    "        q=deque()\n",
    "        for i,x in enumerate(points):\n",
    "            while q and x[0]-points[q[0]][0]>k:\n",
    "                q.popleft()\n",
    "            if q:\n",
    "                ans=max(ans,x[0]-points[q[0]][0]+x[1]+points[q[0]][1])\n",
    "            while q and points[q[-1]][1]-points[q[-1]][0]<=x[1]-x[0]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        ans = -inf\n",
    "        q = deque()\n",
    "        for x, y in points:\n",
    "            while q and q[0][0] < x - k:  # 队首超出范围\n",
    "                q.popleft()  # 弹它！\n",
    "            if q:\n",
    "                ans = max(ans, x + y + q[0][1])  # 加上最大的 yi-xi\n",
    "            while q and q[-1][1] <= y - x:  # 队尾不如新来的强\n",
    "                q.pop()  # 弹它！\n",
    "            q.append((x, y - x))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        # (x, y-x)\n",
    "        # 单调队列确保队首是当前滑动窗口中y-x的最大值\n",
    "        ans = -inf\n",
    "        q = deque()\n",
    "        for x, y in points:\n",
    "            while q and x - q[0][0] > k:\n",
    "                q.popleft()\n",
    "            if len(q)>0:\n",
    "                ans = max(ans, x+y+q[0][1])\n",
    "            while q and y-x >= q[-1][1]:\n",
    "                q.pop()\n",
    "            q.append([x, y-x])\n",
    "            \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        ans=-inf\n",
    "        q=deque()\n",
    "        for x,y in(points):\n",
    "            while q and x-q[0][0]>k:\n",
    "                q.popleft()\n",
    "            if q:\n",
    "                ans=max(ans,x+y+q[0][1])\n",
    "            while q and q[-1][1]<=y-x:\n",
    "                q.pop()\n",
    "            q.append((x,y-x))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        res = -inf\n",
    "        q = deque()\n",
    "        for x, y in points:\n",
    "            # 处理左侧：\n",
    "            while q and x - q[0][0] > k:\n",
    "                q.popleft()\n",
    "\n",
    "            if q:\n",
    "                res = max(res, x + y + q[0][1] - q[0][0])\n",
    "\n",
    "\n",
    "            # 处理右侧\n",
    "            while q and (q[-1][1] - q[-1][0] <= y - x):\n",
    "                q.pop()\n",
    "            q.append((x, y))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        #先变个形,所求为xj+yj+yi-xi,因此枚举xj+yj保存yi-xi最大值，这个最大值可以用特殊结构维护\n",
    "        #因此是前缀最大值，单调队列利于保存这种结构，并且单调队列可以帮助做一些限制性弹出操作(不在范围内的弹出)\n",
    "        #这个是很自然的用这个结构存前缀最大值的方法\n",
    "        q=deque()\n",
    "        ans=-inf\n",
    "        for u,v in points:\n",
    "            #更新答案\n",
    "            #先检查是否合法（对于即将加入的新值，新的范围，考虑这个新最大值如果不合法的先弹出，先加再谈数值一样了），然后再加入新值\n",
    "            while q and (u-q[0][0])>k:\n",
    "                q.popleft()\n",
    "            #队列保证非空\n",
    "            if q:\n",
    "                ans=max(ans,q[0][1]-q[0][0]+u+v)\n",
    "            #入队(不符合要求的弹出)\n",
    "            while q and (v-u)>=(-q[-1][0]+q[-1][1]):\n",
    "                q.pop()\n",
    "            q.append((u,v))\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        left, right = 0, 1\n",
    "        possible = []\n",
    "        ans = -4e8\n",
    "        while left < len(points):\n",
    "            while right < len(points) and points[right][0] - points[left][0] <= k:\n",
    "                if not possible:\n",
    "                    possible.append((points[right][0] + points[right][1], right))\n",
    "                    right += 1\n",
    "                elif points[right][0] + points[right][1] >= possible[-1][0]:\n",
    "                    possible.pop()\n",
    "                else:\n",
    "                    possible.append((points[right][0] + points[right][1], right))\n",
    "                    right += 1\n",
    "            while possible and possible[0][1] <= left:\n",
    "                possible.pop(0)\n",
    "            if possible:\n",
    "                ans = max(ans, possible[0][0] + points[left][1] - points[left][0])\n",
    "            left += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        res,stack = float(\"-inf\"),[]\n",
    "        for x,y in points:\n",
    "            while stack and x - stack[0][1] > k:\n",
    "                heapq.heappop(stack)\n",
    "            if stack:\n",
    "                res = max(res,x + y - stack[0][0])\n",
    "            heapq.heappush(stack,(x - y,x))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        # 方法1: (x-y,x)最大堆\n",
    "        # 因为i<j, 所以xi<xj, 所以yi+yj+|xi-xj|一定等于xj+yj+yi-xi\n",
    "        # 找前面最大的满足要求的yi-xi即可\n",
    "        q = []\n",
    "        n = len(points)\n",
    "        res = -float(\"inf\")\n",
    "        for j in range(n):\n",
    "            xj, yj = points[j]\n",
    "            while q:\n",
    "                sm, xi = q[0]\n",
    "                if xj - xi > k:\n",
    "                    # 距离超过了, 弹出堆顶\n",
    "                    heapq.heappop(q)\n",
    "                else:\n",
    "                    # 当前堆顶满足条件, 更新最终结果\n",
    "                    res = max(res, xj + yj - sm)\n",
    "                    # 注意结束循环!\n",
    "                    break\n",
    "            # 使用x-y, 这样保证堆顶x-y最小, 即y-x最大\n",
    "            heapq.heappush(q, (xj - yj, xj))\n",
    "        return res\n",
    "        # 方法2: (y-x,x)双端单调队列+左大右小\n",
    "        n = len(points)\n",
    "        res = -float(\"inf\")\n",
    "        q = collections.deque()\n",
    "        for x, y in points:\n",
    "            while q and x - q[0][1] > k:\n",
    "                # 弹出左边不满足要求的元组\n",
    "                q.popleft()\n",
    "            if q:\n",
    "                # 此时左边q[0][0]就是最大的yi-xi\n",
    "                res = max(res, x + y + q[0][0])\n",
    "            while q and q[-1][0] <= y - x:\n",
    "                # 弹出右边y-x小于当前值的元组, 因为它们一定不如当前元组\n",
    "                q.pop()\n",
    "            # 追加当前元组\n",
    "            q.append((y - x, x))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        nums = []\n",
    "        heapq.heapify(nums)\n",
    "        ans = -inf\n",
    "        for x, y in points:\n",
    "            while nums and x - nums[0][1] > k:\n",
    "                heapq.heappop(nums)\n",
    "            if nums:\n",
    "                ans = max(ans, x + y -nums[0][0])\n",
    "            heapq.heappush(nums, [x-y, x])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        ans = -inf\n",
    "        q = deque()\n",
    "        for x, y in points:\n",
    "            while q and q[0][0] < x - k:  # 队首超出范围\n",
    "                q.popleft()  # 弹它！\n",
    "            if q:\n",
    "                ans = max(ans, x + y + q[0][1])  # 加上最大的 yi-xi\n",
    "            while q and q[-1][1] <= y - x:  # 队尾不如新来的强\n",
    "                q.pop()  # 弹它！\n",
    "            q.append((x, y - x))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        q = deque()\n",
    "        res = - inf\n",
    "        for x,y in points:\n",
    "            while q and abs(x - q[0][1]) > k:\n",
    "                q.popleft()\n",
    "            if q:\n",
    "                res = max(res, x+y+q[0][0])\n",
    "            while q and y-x >= q[-1][0]:\n",
    "                q.pop()\n",
    "            q.append([y-x,x])\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        length=len(points)\n",
    "        dpsmaller=[0]*length\n",
    "        dpbigger=[0]*length\n",
    "        # a=max(0,1)\n",
    "        for i in range(length):\n",
    "            dpsmaller[i]=points[i][1] - points[i][0]\n",
    "            dpbigger[i]=points[i][1] + points[i][0]\n",
    "        ans=-200000000\n",
    "        # for i in range(length-1):\n",
    "        #     smaller=dpsmaller[i]\n",
    "        #     for j in range(i+1,length):\n",
    "        #         if(points[j][0]-points[i][0]>k):\n",
    "        #             break\n",
    "        #     if(j==i+1):\n",
    "        #         if(points[j][0]-points[i][0]<=k):\n",
    "        #             bigger=dpbigger[j]\n",
    "        #             ans=max(smaller+bigger,ans)\n",
    "        #         continue\n",
    "        #     if(j==length-1):\n",
    "        #         if(points[j][0]-points[i][0]<=k):\n",
    "        #             j+=1\n",
    "        #     # if(j==i+2):\n",
    "        #     #     bigger=dpbigger[i+1]\n",
    "        #     #     ans=max(smaller+bigger,ans)\n",
    "        #     # else:\n",
    "        #     bigger=max(dpbigger[i+1:j])\n",
    "        #     ans=max(smaller+bigger,ans)\n",
    "        tmpi=-1\n",
    "        tmpj=-1\n",
    "        def max_def(nums):\n",
    "            ret_num=nums[0]\n",
    "            ret_i=0\n",
    "            for i in range(len(nums)):\n",
    "                if(ret_num<nums[i]):\n",
    "                    ret_i=i\n",
    "                    ret_num=nums[i]\n",
    "            return ret_num,ret_i\n",
    "        for i in range(length-1):\n",
    "            smaller=dpsmaller[i]\n",
    "            left=i\n",
    "            right=length-1\n",
    "            while(left<right):\n",
    "                middle=(left+right)//2\n",
    "                tmp=points[middle][0]-points[i][0]\n",
    "                # print(middle,left,right)\n",
    "                if(tmp<=k):\n",
    "                    left=middle+1\n",
    "                else:\n",
    "                    right=middle\n",
    "            if(points[left][0]-points[i][0]>k):\n",
    "                j=left-1\n",
    "            else:\n",
    "                j=left\n",
    "            if(j==i):\n",
    "                if(points[i+1][0]-points[i][0]<=k):\n",
    "                    bigger=dpbigger[i+1]\n",
    "                    ans=max(smaller+bigger,ans)\n",
    "                continue\n",
    "            # print(i,j)\n",
    "            if(tmpi<i+1):\n",
    "                bigger,tmpi=max_def(dpbigger[i+1:j+1])\n",
    "                # tmpi为本次最大值对应的点\n",
    "                tmpj=j\n",
    "                tmpi+=i+1\n",
    "            else:\n",
    "                if(tmpj<j):\n",
    "                    bigger2,tmpi2=max_def(dpbigger[tmpj:j+1])\n",
    "                    tmpi2+=tmpj\n",
    "                    tmpj=j\n",
    "                    if(dpbigger[tmpi]<=dpbigger[tmpi2]):\n",
    "                        tmpi=tmpi2\n",
    "                    bigger=dpbigger[tmpi]\n",
    "            # print(i,j,smaller,bigger)\n",
    "            ans=max(smaller+bigger,ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=1499 lang=python3\n",
    "#\n",
    "# [1499] 满足不等式的最大值\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "import sortedcontainers\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        n = len(points)\n",
    "        q = SortedList()\n",
    "        ans = -inf\n",
    "        l = 0\n",
    "        for i in range(n-1):\n",
    "            q.add((points[i][1] - points[i][0], points[i][0]))\n",
    "            while q and points[i+1][0] - points[l][0] > k:\n",
    "                q.remove((points[l][1] - points[l][0], points[l][0]))\n",
    "                l += 1\n",
    "            if q: ans = max(ans, sum(points[i+1]) + q[-1][0])\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        n = len(points)\n",
    "        pre, res = 0, -inf\n",
    "        q = deque()\n",
    "        q.append([points[0][0], points[0][1] - points[0][0]])\n",
    "        for i in range(1, n):\n",
    "            # print(q, i, points[i][1] + points[i][0])\n",
    "            while len(q) > 0 and points[i][0] - q[0][0] > k:\n",
    "                q.popleft()\n",
    "            if len(q) > 0:\n",
    "                res = max(res, points[i][1] + points[i][0] + q[0][1])    \n",
    "            while len(q) > 0 and q[-1][1] < points[i][1] - points[i][0]:\n",
    "                q.pop()\n",
    "            q.append([points[i][0], points[i][1] - points[i][0]])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "inf = -float('inf')\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        n,l = len(points),0\n",
    "        tree = SortedList()\n",
    "        ans = -float('inf')\n",
    "        for i in range(n):\n",
    "            while l < i and points[i][0] - points[l][0] > k:\n",
    "                tree.remove(points[l][1] - points[l][0])\n",
    "                l += 1\n",
    "            if len(tree):\n",
    "                ans = max(ans,tree[-1] + points[i][0] + points[i][1])\n",
    "            tree.add(points[i][1] - points[i][0])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        # 拆分函数\n",
    "        n = len(points)\n",
    "        from sortedcontainers import SortedList\n",
    "        ans = -10**18\n",
    "        points.sort()\n",
    "        sli = SortedList()\n",
    "        l = 0\n",
    "        for x,y in points:\n",
    "            while x - points[l][0] > k:\n",
    "                sli.remove(points[l][1] - points[l][0])\n",
    "                l += 1\n",
    "            if sli:\n",
    "                ans = max(y + x + sli[-1],ans)\n",
    "            sli.add(y - x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        ans = -inf\n",
    "        j = 0\n",
    "        n = len(points)\n",
    "\n",
    "        q = deque()\n",
    "        points.append([inf, 0])\n",
    "\n",
    "        for i in range(n):\n",
    "            x, y = points[i]\n",
    "\n",
    "            if i == j:\n",
    "                j = i + 1\n",
    "            \n",
    "            while points[j][0] <= x + k:\n",
    "                t = points[j][0] + points[j][1]\n",
    "\n",
    "                while q and t >= q[-1][0]:\n",
    "                    q.pop()\n",
    "                \n",
    "                q.append((t, j))\n",
    "                j += 1\n",
    "\n",
    "            while q and i >= q[0][1]:\n",
    "                q.popleft()\n",
    "            \n",
    "            if q:\n",
    "                ans = max(ans, y - x + q[0][0])\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        j = 0\n",
    "        n = len(points)\n",
    "        q = PriorityQueue()\n",
    "        ret = - 2 ** 50\n",
    "        for i in range(n):\n",
    "            x1, y1 = points[i]\n",
    "            while j < n and points[j][0] - x1 <= k:\n",
    "                q.put((sum(points[j]) * -1, j))\n",
    "                j += 1\n",
    "            \n",
    "            while not q.empty() and q.queue[0][1] <= i:\n",
    "                q.get()\n",
    "            if not q.empty():\n",
    "                ret = max(ret, y1 - x1 + q.queue[0][0] * -1)\n",
    "        return ret\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        from sortedcontainers import SortedList \n",
    "        sl = SortedList()\n",
    "        n = len(points)\n",
    "        left,right = 0,1 \n",
    "        ans = -inf\n",
    "        for left in range(n-1):\n",
    "            while right<n and points[right][0]-points[left][0]<=k:\n",
    "                sl.add((points[right][0]+points[right][1],points[right][0]))\n",
    "                right+=1\n",
    "            res = points[left][1]-points[left][0]\n",
    "            while sl and sl[-1][1]<=points[left][0]:\n",
    "                sl.pop()\n",
    "            if sl:\n",
    "                res+=sl[-1][0]\n",
    "                ans = max(res,ans)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:\n",
    "        t = 0\n",
    "        h = 0\n",
    "        ans = -1000000000\n",
    "        n = len(points)\n",
    "        arr = [0 for _ in range(100000)]\n",
    "        for i in range(n):\n",
    "            while h < t and points[i][0] - points[arr[h]][0] > k:\n",
    "                h += 1\n",
    "            if h < t:\n",
    "                ans = max(ans, points[i][1] + points[i][0] + points[arr[h]][1] - points[arr[h]][0]) \n",
    "            while h < t and points[i][1] - points[i][0] >= points[arr[t-1]][1] - points[arr[t-1]][0]:\n",
    "                t -= 1\n",
    "            arr[t] = i\n",
    "            t += 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
